#include <vector>

using namespace std;

/* 计数排序 */
// 完整实现，可排序对象，并且是稳定排序
void countingSort(vector<int>& nums) {
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    int n = nums.size();
    vector<int> res(n);
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num;
        counter[num]--;
    }
    nums = res;
}
